package mine.personal.demo.pratice.algorithm.dynamicprogramming.multistatus;

import java.util.Arrays;

/**
 * @Author: lhl
 * @CreateTime: 2025-04-14
 * @Description: 多状态动态规划
 * @Version: 1.0
 */
public class Solution {

    /**
     * leetcode -> 按摩师/打家劫舍I
     * @author: 李鸿麟
     * @date: 2025/4/14
     * @param: nums
     * @return: int
     */
    public int massage(int[] nums) {
        int n = nums.length;
        // 边界条件处理
        if (n == 0) {
            return 0;
        }
        // f表示在i位置时 nums[i]必选 此时总时长最大
        int[] f = new int[n];
        // g表示在i位置时 nums[i]不选 此时总时长最大
        int[] g = new int[n];

        // 初始化
        f[0] = nums[0]; g[0] = 0;
        for (int i = 1; i < n; i++) {
            f[i] = g[i - 1] + nums[i];
            g[i] = Math.max(f[i - 1], g[i - 1]);
        }
        return Math.max(f[n - 1], g[n - 1]);
    }

    /**
     * leetcode -> 打家劫舍II
     * @author: 李鸿麟
     * @date: 2025/4/15
     * @param: nums
     * @return: int
     */
    public int rob(int[] nums) {
        int n = nums.length;
        // 偷第一间房屋
        int max1 = robRange(nums, 2, n - 2);
        // 不偷第一间房屋
        int max2 = robRange(nums, 1, n - 1);
        return Math.max(nums[0] + max1, max2);
    }

    private int robRange(int[] nums, int left, int right) {
        if (left > right) {
            return 0;
        }
        int[] f = new int[nums.length];
        int[] g = new int[nums.length];
        f[left] = nums[left];
        for (int i = left+1; i <=right; i++) {
            f[i] = g[i - 1] + nums[i];
            g[i] = Math.max(g[i - 1], f[i - 1]);
        }
        return Math.max(f[right],g[right]);
    }

    /**
     * leetcode -> 删除并获得点数
     * 做新的算法题 一定要往已知的模板或者是经验上套
     * @author: 李鸿麟
     * @date: 2025/4/16
     * @param: nums
     * @return: int
     */
    public int deleteAndEarn(int[] nums) {
        int n = nums.length;
        Arrays.sort(nums);
        int m = nums[n - 1];
        int[] arr = new int[m + 1];

        // 初始化arr
        for (int i = 0; i < n; i++) {
            int tmp = nums[i];
            arr[tmp] += tmp;
        }

        // 对arr进行"打家劫舍"
        int[] f = new int[m + 1];
        int[] g = new int[m + 1];
        f[0] = arr[0];
        for (int i = 1; i <= m; i++) {
            f[i] = g[i - 1] + arr[i];
            g[i] = Math.max(g[i - 1], f[i - 1]);
        }

        return Math.max(g[m], f[m]);
    }

    /**
     * leetcode -> 粉刷房子
     * @author: 李鸿麟
     * @date: 2025/4/17
     * @param: costs
     * @return: int
     */
    public int minCost(int[][] costs) {
        int n = costs.length;
        if (n == 0) {
            return 0;
        }
        int red = costs[0][0];
        int blue = costs[0][1];
        int green = costs[0][2];
        for (int i = 1; i < n; i++) {
            int prevRed = red;
            int prevBlue = blue;
            int prevGreen = green;
            red = costs[i][0] + Math.min(prevBlue, prevGreen);
            blue = costs[i][1] + Math.min(prevRed, prevGreen);
            green = costs[i][2] + Math.min(prevRed, prevBlue);
        }
        return Math.min(Math.min(red, blue), green);
    }

    /**
     * leetcode -> 买卖股票的最佳时机含冷冻期
     * @author: 李鸿麟
     * @date: 2025/4/19
     * @param: prices
     * @return: int
     */
    public static int maxProfit(int[] prices) {
        int n = prices.length;
        // dp[i][0] 表示买入 dp[i][1]表示可交易 dp[i][2]表示冷冻期
        int[][] dp = new int[n][3];
        dp[0][0] = - prices[0];

        for (int i = 1; i < n; i++) {
            dp[i][0] = Math.max(dp[i - 1][1] - prices[i], dp[i - 1][0]);
            dp[i][1] = Math.max(dp[i - 1][1], dp[i - 1][2]);
            dp[i][2] = dp[i - 1][0] + prices[i];
        }
        return Math.max(Math.max(dp[n - 1][0], dp[n - 1][1]), dp[n - 1][2]);
    }

    /**
     * leetcode -> 买卖股票的最佳时机含手续费
     * @author: 李鸿麟
     * @date: 2025/4/21
     * @param: prices
     * @param: fee
     * @return: int
     */
    public int maxProfit(int[] prices, int fee) {
        int n = prices.length;
        // dp[0][i]表示第i天结束买入(手中持有股票的状态)状态的最大利润 dp[1][i]表示第i天结束可交易(手中未持有股票的状态)状态的最大利润
        int[][] dp = new int[2][n];
        dp[0][0] = -prices[0];
        for (int i = 1; i < n; i++) {
            // 买入状态可选的操作有两种 第一:从可交易状态以第i天的股价买入股票 或者啥也不干
            dp[0][i] = Math.max(dp[1][i - 1] - prices[i], dp[0][i - 1]);
            // 可交易状态可选的操作有两种 第一:从买入状态以第i天的股价卖出股票 或者啥也不干
            dp[1][i] = Math.max(dp[0][i - 1] + prices[i] - fee, dp[1][i - 1]);
        }
        return Math.max(dp[1][n - 1], dp[0][n - 1]);
    }

    /**
     * leetcode -> 买卖股票问题III(限制交易次数为2次)
     * @author: 李鸿麟
     * @date: 2025/4/22
     * @param: prices
     * @return: int
     */
    public int maxProfitIII(int[] prices) {
        int n = prices.length;
        // f表示买入状态(手中持有股票) f[i][j]表示第i天结束 完成了j笔交易 处于买入状态的最大利润
        int[][] f = new int[n][3];
        // g表示卖出状态(手中未持有股票) g[i][j]表示第i天结束 完成了j笔交易 处于卖出状态的最大利润
        int[][] g = new int[n][3];

        // 初始化
        f[0][0] = -prices[0];
        // 顶级细节 选择这个值不会出现编译器报错 也能避免干扰
        f[0][1] = f[0][2] = -0x3f3f3f;

        for (int i = 1; i < n; i++) {
            for (int j = 0; j < 3; j++) {
                f[i][j] = Math.max(f[i - 1][j], g[i - 1][j] - prices[i]);
                if (j - 1 >= 0) {
                    g[i][j] = Math.max(g[i - 1][j], f[i - 1][j - 1] + prices[i]);
                } else {
                    g[i][j] = g[i - 1][j];
                }
            }
        }
        int ret = Integer.MIN_VALUE;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < 3; j++) {
                if (ret < g[i][j]) {
                    ret = g[i][j];
                }
            }
        }
        return ret;
    }

    /**
     * leetcode -> 买卖股票问题IV(限制交易次数为k次)
     * @author: 李鸿麟
     * @date: 2025/4/22
     * @param: k
     * @param: prices
     * @return: int
     */
    public int maxProfitIV(int k, int[] prices) {
        int n = prices.length;
        // f表示买入状态(手中持有股票)
        int[][] f = new int[n][k + 1];
        // g表示卖出状态(手中未持有股票)
        int[][] g = new int[n][k + 1];

        // 初始化
        f[0][0] = -prices[0];
        for (int i = 1; i <= k; i++) {
            f[0][i] = -0x3f3f3f;
        }


        for (int i = 1; i < n; i++) {
            for (int j = 0; j <= k; j++) {
                f[i][j] = Math.max(f[i - 1][j], g[i - 1][j] - prices[i]);
                if (j - 1 >= 0) {
                    g[i][j] = Math.max(g[i - 1][j], f[i - 1][j - 1] + prices[i]);
                } else {
                    g[i][j] = g[i - 1][j];
                }
            }
        }
        int ret = Integer.MIN_VALUE;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j <= k; j++) {
                if (ret < g[i][j]) {
                    ret = g[i][j];
                }
            }
        }
        return ret;
    }
}
